|
|
Automatic Creation of Organ Overtures for Church Songs
Maňák, Ondřej ; Černocký, Jan (referee) ; Fapšo, Michal (advisor)
The focus of this master's thesis is an automatic creation of organ overtures for church songs from both theoretical and practical points of view. Organ overture is a short introduction to a church song. According to the fact that it can be described by a finite set of rules, it is possible to use techniques for solving Constraint Satisfaction Problems. An effective instrument to develop such system can be C++ programming language and Gecode library.
|
|
|
Rule-Based Melody Harmonization
Kuchár, Pavol ; Žák, Pavel (referee) ; Fapšo, Michal (advisor)
Bachelor thesis deals with the issue of computer aided composition. The aim of the thesis was to create the program, which implements several rules of music theory and using of CSP determines appropriate tones for harmonization of melody. The result is presented in score and MIDI file.
|
|
|
Automatic jazz arrangement
Chadim, Petr ; Karafiát, Martin (referee) ; Fapšo, Michal (advisor)
This Thesis is focused on the arranging of the melody, which is accompanied by jazz chords. It deals with creating a more harmonious voices using Block Voicing method. Distribution to target notes and passing notes is made using techniques of constraint programming (CSP). Passing notes are reharmonized by dominant seventh chord or by parallel chord. Using CSP a bass part is also created. To solve CSP is used Gecode library. The harmonious voices are arranged by Four Part Close Voicing. The application result is a tool for the music arranger.
|
|
|
Graphic Animation of Problem Solving Methods
Macek, Jiří ; Jurka, Pavel (referee) ; Zbořil, František (advisor)
There are many kinds of implementation artificial intelligence for automatic solving problems by computer technology. The main topics of this bachelor's thesis are some typical methods, describing of their features, comparing them among and shows some useful techniques of algoritmization and implementation too. Main purpose of this thesis is creating application, which clearly demonstrates at chosen problems methods of their solving.
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (advisor) ; Pergel, Martin (referee)
The thesis is focused on the Sivia algorithm (Set Inverter via Interval Ana- lysis) designed for solving a continuous constraint satisfaction problem using interval methods and propagation techniques. Basic properties of the algorithm are derived, including the correction of its presented complexity bound. Some improvements concerning the testing of constraint satisfaction and optimiza- tion of the number of interval boxes describing the solution are proposed. The thesis also introduces contractors used to enhance the effectivity of the Sivia algorithm by reducing the interval boxes processed. Presented algorithms were implemented in a solver for nonlinear constraints with a simple visualization of the result using the Matlab language. A comparison of basic contractors on specific examples is given.
|
|
|
Airport - Time and resource constrained project sheduling
Vandas, Marek ; Petříčková, Zuzana (advisor) ; Pangrác, Ondřej (referee)
This thesis identifies constraints for safe ground airport operations. These operations consist of runway assignment, taxi operations planning and gate scheduling. The aim of this thesis is to show how this problem can be formulated as constraint satisfaction problem and then solved as a scheduling problem. Based on this model, an application that ilustrates these concepts is designed and implemented. This application enables a visualisation of results. An extendable constraint solver was implemented for the purpose of this application. This solver can be used to solve problems from other domains as well and also enables easy change of search strategy.
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
|
|
Interval linear and nonlinear systems
Horáček, Jaroslav ; Hladík, Milan (advisor) ; Garloff, Jürgen (referee) ; Ratschan, Stefan (referee)
First, basic aspects of interval analysis, roles of intervals and their applications are addressed. Then, various classes of interval matrices are described and their relations are depicted. This material forms a prelude to the unifying theme of the rest of the work - solving interval linear systems. Several methods for enclosing the solution set of square and overdetermined interval linear systems are covered and compared. For square systems the new shaving method is introduced, for overdetermined systems the new subsquares approach is introduced. Detecting unsolvability and solvability of such systems is discussed and several polynomial conditions are compared. Two strongest condi- tions are proved to be equivalent under certain assumption. Solving of interval linear systems is used to approach other problems in the rest of the work. Computing enclosures of determinants of interval matrices is addressed. NP- hardness of both relative and absolute approximation is proved. New method based on solving square interval linear systems and Cramer's rule is designed. Various classes of matrices with polynomially computable bounds on determinant are characterized. Solving of interval linear systems is also used to compute the least squares linear and nonlinear interval regression. It is then applied to real...
|
|
|
Generalizing CSP-related results to infinite algebras
Olšák, Miroslav ; Barto, Libor (advisor) ; Zhuk, Dmitrii (referee) ; Pinsker, Michael (referee)
The recent research on constraint satisfaction problems (CSPs) on fixed finite templates provided useful tools for computational complexity and universal algebra. However, the research mainly focused on finite relational structures, and consequently, finite algebras. We pursue a generalization of these tools and results into the domain of infinite algebras. In particular, we show that despite the fact that the Maltsev condition s(r, a, r, e) = s(a, r, e, a) does not characterize Taylor algebras (i.e., algebras that satisfy a nontrivial idem- potent Maltsev condition) in general, as it does in the finite case, there is another strong Maltsev condition characterizing Taylor algebras, and s(r, a, r, e) = s(a, r, e, a) characterizes another interesting broad class of algebras. We also provide a (weak) Maltsev condition for SD(∧) algebras (i.e., algebras that satisfy an idem- potent Maltsev condition not satisfiable in a module). Beyond Maltsev conditions, we study loop lemmata and, in particular, reprove a well known finite loop lemma by two different general (infinite) approaches.
|
|
|
Visualisation of interval data
Mečiar, Martin ; Horáček, Jaroslav (advisor) ; Rada, Miroslav (referee)
The thesis is focused on visualisation, comparison and modification of outputs of interval solvers for solving a continuous constraint satisfaction problem. The author's designed solution for the approximation of outputs of solvers is presented in the thesis. The approximation of outputs of solvers is transformed into the problem of visual reallocation of the sets of outputs of solvers on a finer level than interval box level. Main part of the thesis is the program on added CD that allows visualisation, comparison and modification of outputs of interval solvers. The program is written in C++, but can be compiled as a MEX file for MATLAB. A user documentation and a technical documentation for the program are included in the thesis. The thesis shows several examples of program output in the devoted chapter. Powered by TCPDF (www.tcpdf.org)
|
guest ::
